package com.zhanghp.class025;

import static com.zhanghp.common.ArrUtil.print;
import static com.zhanghp.common.ArrUtil.swap;

/**
 * 小跟堆 大 -》 小
 *
 * @author zhanghp
 * @since 2024/3/29 11:55
 */
public class HeapSort2 {

    // 小跟堆

    /**
     * 向上调整
     *
     * @param arr
     * @param i
     */
    public static void heapify(int[] arr, int i) {
        while (arr[i] < arr[(i - 1) / 2]) {
            swap(arr, i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }

    /**
     * 向下调整
     *
     * @param arr
     * @param i
     * @param size
     */
    public static void heapInsert(int[] arr, int i, int size) {
        int l = (i << 1) + 1;
        while (l < size) {
            int best = (l + 1) < size && arr[l + 1] < arr[l] ? l + 1 : l;
            if (arr[i] < arr[best]) {
                return;
            }
            swap(arr, i, best);
            i = best;
            l = (i << 1) + 1;
        }
    }

    // 小跟堆排序 和本节练习题无关 大 -》 小
    public static void sort(int[] arr){
        // 变成小跟堆
        for (int i = 0; i < arr.length; i++) {
            heapify(arr, i);
        }
        // 排序
        int size = arr.length;
        while (size > 1) {
            swap(arr, 0, --size);
            heapInsert(arr, 0, size);
        }
        print(arr);
    }
}
